//#region 路径问题

/**797. 所有可能的路径-有向图-深搜 
 * - 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
 * -  graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
 */
export function allPathsSourceTarget(graph: number[][] = [[1, 2], [3], [3], []]): number[][] {
    //根据题目描述， graph[i]代表节点i的邻接节点

    /**结果 */
    const res: number[][] = []
    /**路径数组 */
    const path: number[] = [0]
    /**深度优先搜索
     * @param x 当前是遍历第几个节点(graph的索引) 
     */
    const dfs = (x: number) => {
        if (x === graph.length - 1) {//递归终止条件 
            res.push([...path])
            return
        }
        for (let i = 0; i < graph[x].length; i++) {//遍历当前节点连接的所有节点 
            path.push(graph[x][i])
            dfs(graph[x][i])//递归下一个节点
            path.pop() //回溯
        }
    }
    dfs(0)
    return res
}
/**127. 单词接龙-无向图-广搜
 * - 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
 * - 每一对相邻的单词只差一个字
 * - 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 
 */
export function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    //题目省流：找从 beginWord 到 endWord 的最短路径的长度。 wordList中只相差一个字母的单词之间才存在路径 
    //     无向图找最短路径，用广搜最合适，因为一但找到终点，说明就是最短路径

    /**将wordList转成Set，提高查询速度 */
    const wordSet = new Set(wordList);
    if (wordSet.size === 0 || !wordSet.has(endWord)) return 0; // Set元素个数为0 或者 endWord没有在wordSet出现，直接返回0
    /**记录word是否访问过  <word, 到这个word的路径长度>*/
    const visitMap = new Map<string, number>();
    /**bfs队列 */
    const queue: string[] = [];
    queue.push(beginWord);//初始化队列 
    visitMap.set(beginWord, 1);// 初始化visitMap
    while (queue.length) {
        /**取出队头元素 */
        const word = queue.shift()!
        /**这个word的路径长度 */
        const path = visitMap.get(word)!;
        for (let i = 0; i < word.length; i++) { // 遍历单词的每个字符
            for (let c = 97; c <= 122; c++) { // 对应26个字母ASCII值 从'a' 到 'z' 遍历替换
                /**拼串得到新的字符串 */
                let newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
                if (newWord === endWord) return path + 1; //如果得到的就是终点，返回path+1
                // wordSet出现了newWord，并且newWord没有被访问过
                if (wordSet.has(newWord) && !visitMap.has(newWord)) {
                    visitMap.set(newWord, path + 1);// 添加访问信息
                    queue.push(newWord);
                }
            }
        }
    }



    return 0
};
/**841. 钥匙和房间-有向图-深搜
 * - 当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
 * - 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
 */
export function canVisitAllRooms(rooms: number[][] = [[1], [2], [3], []]): boolean {
    /**记录访问过的节点 */
    const visited = new Array<boolean>(rooms.length).fill(false)
    visited[0] = true
    /**深搜。key是当前房间索引(也就是打开这个房间的钥匙) */
    const dfs = (key: number) => {
        if (visited[key]) {//如果是打开过的房间就结束本次递归
            return
        }
        visited[key] = true //打开房间
        for (let i = 0; i < rooms[key].length; i++) {//遍历当前房间的所有钥匙 
            dfs(rooms[key][i])
        }
    }
    for (let i = 0; i < rooms[0].length; i++) { //从第0个房间开始
        dfs(rooms[0][i])
    }
    for (let i = 0; i < visited.length; i++) { //判断是否有的没访问到
        if (!visited[i]) return false
    }
    return true
}

//#endregion